#include <stdio.h>

#define LENGTH 100

void swap_int(int* data,int a,int b){
	int temp=data[a];
	data[a]=data[b];
	data[b]=temp;
}

void swapa(int data[],int low,int mid,int high){
	printf("swap %d,%d,%d\n",low,mid,high);
	if(low==mid){
		if(data[mid]<data[high])
			swap_int(data,mid,high);
	}
	int high_long= ( (high-mid)>(mid-low+1)?0:1);
	int* temp;
	if(high_long){
		temp=(int*)malloc(sizeof(int)*(mid-low+1));
		int i;
		//copy low to temp
		for(i=low;i<mid+1;i++){
			temp[i-low]=data[i];
		}
		//move high to low
		int j;
		for(i=mid,j=low;i<high+1;i++,j++){
			data[j]=data[i];
		}
		//copy back low
		int st=j;
		for(;j<high+1;j++){
			data[j]=temp[j-st];
		}
	}else{
		printf("can't process %d,%d,%d\n",low,mid,high);
	}
	
}

int cmp(const void * l,const void * r ){
	return *(int*)l-*(int*)r;
}

int qcount=0;

void merge(int data[],int low,int mid,int high){
	qsort(data,high-low,sizeof(int),cmp);
	qcount++;
}

int mcount=0;
void mergeSort(int data[],int low,int high){
	int mid;
	mcount++;
	//printf("%d,%d\n",low,high);
	if(low<high && high>0){
		mid=(low+high)/2;
		mergeSort(data,low,mid);
		mergeSort(data,mid+1,high);
		merge(data,low,mid,high);
	}
}

void printData(int data[],int size){
	int i;
	for(i=0;i<size;i++){
		printf("%d\t",data[i]);
	}
	printf("\n");
}

int main(){
	int* data=(int*)malloc(sizeof(int)*LENGTH);
	int i;
	for(i=0;i<LENGTH;i++)
		data[i]=rand()%10000;
	printData(data,LENGTH);
	
	mergeSort(data,0,LENGTH-1);
	printf("result:\n");
	printData(data,LENGTH);
	
	printf("\nqsort:%d\nmcount:%d\n",qcount,mcount);
	return 0;
}
